home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / vol_200 / 244_01 / three41.c < prev    next >
Encoding:
C/C++ Source or Header  |  1987-10-24  |  8.9 KB  |  333 lines
  1.  
  2. /* program to analyze the de Bruijn diagram of a cellular */
  3. /* automaton and report all the periodic states. */
  4. /* version for totalistic (4,1), third generation */
  5. /* [Harold V. McIntosh, 4 May 1987] */
  6.  
  7. # include <stdio.h>
  8.  
  9. # define MC     8                /* maximum number of columns */
  10. # define NS     10                /* number of distinct sums */
  11. # define ML    24                /* pause after so many lines */
  12.  
  13. char arry[4][4][4][4][4][4][4];
  14. int  rule[NS] = 0,1,0,0,1,2,1,2,3,3;
  15. int  nc, nl;
  16.  
  17. main() {
  18. int i;
  19.  
  20. printf("Rule number:\n");
  21. printf("0..1..2..3\n");
  22. for (i=0; i<NS; i++) rule[i]=getchar()-'0';
  23.  
  24. nc=0;
  25. nl=0;
  26.  
  27. printf("\n - several minutes may elapse for each case - \n");
  28.  
  29. kwait(0); printf("Strings conforming to (3,0):"); kwait(0);
  30. pass1a();
  31. pass2i();
  32. pass2o();
  33. pass4();
  34.  
  35. kwait(0); printf("Strings conforming to (3,1):"); kwait(0);
  36. pass1b();
  37. pass2i();
  38. pass2o();
  39. pass4();
  40.  
  41. kwait(0); printf("Strings conforming to (3,2):"); kwait(0);
  42. pass1c();
  43. pass2i();
  44. pass2o();
  45. pass4();
  46.  
  47. kwait(0); printf("Strings conforming to (3,3):"); kwait(0);
  48. pass1d();
  49. pass2i();
  50. pass2o();
  51. pass4();
  52.  
  53. } /* end of main */
  54.  
  55. pass1a() {            /* mark sequences conforming to (3,0) */
  56. int i0, i1, i2, i3, i4, i5, i6;
  57. int j0, j1, j2, j3, j4;
  58. int i, j, k;
  59. printf(" pass1a\015");
  60. for (i0=0; i0<4; i0++) {
  61. for (i1=0; i1<4; i1++) {
  62. for (i2=0; i2<4; i2++) {
  63. for (i3=0; i3<4; i3++) {
  64. for (i4=0; i4<4; i4++) {
  65. for (i5=0; i5<4; i5++) {
  66. for (i6=0; i6<4; i6++) {
  67. j0=rule[i0+i1+i2];
  68. j1=rule[i1+i2+i3];
  69. j2=rule[i2+i3+i4];
  70. j3=rule[i3+i4+i5];
  71. j4=rule[i4+i5+i6];
  72. i=rule[j0+j1+j2];
  73. j=rule[j1+j2+j3];
  74. k=rule[j2+j3+j4];
  75. arry[i0][i1][i2][i3][i4][i5][i6]=rule[i+j+k]==i3?'Y':'N';
  76. };};};};};};};
  77. }
  78.  
  79. pass1b() {            /* mark sequences conforming to (3,1) */
  80. int i0, i1, i2, i3, i4, i5, i6;
  81. int j0, j1, j2, j3, j4;
  82. int  i, j, k;
  83. printf(" pass1b\015");
  84. for (i0=0; i0<4; i0++) {
  85. for (i1=0; i1<4; i1++) {
  86. for (i2=0; i2<4; i2++) {
  87. for (i3=0; i3<4; i3++) {
  88. for (i4=0; i4<4; i4++) {
  89. for (i5=0; i5<4; i5++) {
  90. for (i6=0; i6<4; i6++) {
  91. j0=rule[i0+i1+i2];
  92. j1=rule[i1+i2+i3];
  93. j2=rule[i2+i3+i4];
  94. j3=rule[i3+i4+i5];
  95. j4=rule[i4+i5+i6];
  96. i=rule[j0+j1+j2];
  97. j=rule[j1+j2+j3];
  98. k=rule[j2+j3+j4];
  99. arry[i0][i1][i2][i3][i4][i5][i6]=rule[i+j+k]==i2?'Y':'N';
  100. };};};};};};};
  101. }
  102.  
  103. pass1c() {            /* mark sequences conforming to (3,2) */
  104. int i0, i1, i2, i3, i4, i5, i6;
  105. int j0, j1, j2, j3, j4;
  106. int i, j, k;
  107. printf(" pass1c\015");
  108. for (i0=0; i0<4; i0++) {
  109. for (i1=0; i1<4; i1++) {
  110. for (i2=0; i2<4; i2++) {
  111. for (i3=0; i3<4; i3++) {
  112. for (i4=0; i4<4; i4++) {
  113. for (i5=0; i5<4; i5++) {
  114. for (i6=0; i6<4; i6++) {
  115. j0=rule[i0+i1+i2];
  116. j1=rule[i1+i2+i3];
  117. j2=rule[i2+i3+i4];
  118. j3=rule[i3+i4+i5];
  119. j4=rule[i4+i5+i6];
  120. i=rule[j0+j1+j2];
  121. j=rule[j1+j2+j3];
  122. k=rule[j2+j3+j4];
  123. arry[i0][i1][i2][i3][i4][i5][i6]=rule[i+j+k]==i1?'Y':'N';
  124. };};};};};};};
  125. }
  126.  
  127. pass1d() {            /* mark sequences conforming to (3,3) */
  128. int i0, i1, i2, i3, i4, i5, i6;
  129. int j0, j1, j2, j3, j4;
  130. int i, j, k;
  131. printf(" pass1d\015");
  132. for (i0=0; i0<4; i0++) {
  133. for (i1=0; i1<4; i1++) {
  134. for (i2=0; i2<4; i2++) {
  135. for (i3=0; i3<4; i3++) {
  136. for (i4=0; i4<4; i4++) {
  137. for (i5=0; i5<4; i5++) {
  138. for (i6=0; i6<4; i6++) {
  139. j0=rule[i0+i1+i2];
  140. j1=rule[i1+i2+i3];
  141. j2=rule[i2+i3+i4];
  142. j3=rule[i3+i4+i5];
  143. j4=rule[i4+i5+i6];
  144. i=rule[j0+j1+j2];
  145. j=rule[j1+j2+j3];
  146. k=rule[j2+j3+j4];
  147. arry[i0][i1][i2][i3][i4][i5][i6]=rule[i+j+k]==i0?'Y':'N';
  148. };};};};};};};
  149. }
  150.  
  151. /* Pass2i flags links which have an incoming arrow */
  152. pass2i() {int i0, i1, i2, i3, i4, i5, i6, l, m;
  153. do {
  154. printf(" pass2i\015");
  155. for (i0=0; i0<4; i0++) {
  156. for (i1=0; i1<4; i1++) {
  157. for (i2=0; i2<4; i2++) {
  158. for (i3=0; i3<4; i3++) {
  159. for (i4=0; i4<4; i4++) {
  160. for (i5=0; i5<4; i5++) {
  161. for (i6=0; i6<4; i6++) {
  162. if ((arry[i0][i1][i2][i3][i4][i5][i6]&0x5F)=='Y')
  163.  {for (m=0; m<4; m++) arry[i1][i2][i3][i4][i5][i6][m]|=0x20;};
  164. };};};};};};};
  165. l=pass3();        /* erase flage, mark survivors, count changes */
  166. } while (l!=0); }
  167.  
  168. /* Pass2o flags links which have an outgoing arrow */
  169. pass2o() {int i0, i1, i2, i3, i4, i5, i6, l, m;
  170. do {
  171. printf(" pass2o\015");
  172. for (i0=0; i0<4; i0++) {
  173. for (i1=0; i1<4; i1++) {
  174. for (i2=0; i2<4; i2++) {
  175. for (i3=0; i3<4; i3++) {
  176. for (i4=0; i4<4; i4++) {
  177. for (i5=0; i5<4; i5++) {
  178. for (i6=0; i6<4; i6++) {
  179. if ((arry[i0][i1][i2][i3][i4][i5][i6]&0x5F)=='Y')
  180.  {for (m=0; m<4; m++) arry[m][i0][i1][i2][i3][i4][i5]|=0x20;};
  181. };};};};};};};
  182. l=pass3();        /* erase flags, mark survivors, count changes */
  183. } while (l!=0); }
  184.  
  185. /* printf("pass3 - erase flags, mark survivors, count channges\n"); */
  186. int pass3() {int i0, i1, i2, i3, i4, i5, i6, l;    /* mark states still linked */
  187. l=0;
  188. printf(" pass3 \015");
  189. for (i0=0; i0<4; i0++) {
  190. for (i1=0; i1<4; i1++) {
  191. for (i2=0; i2<4; i2++) {
  192. for (i3=0; i3<4; i3++) {
  193. for (i4=0; i4<4; i4++) {
  194. for (i5=0; i5<4; i5++) {
  195. for (i6=0; i6<4; i6++) {
  196. switch (arry[i0][i1][i2][i3][i4][i5][i6]) {
  197.     case 'y': arry[i0][i1][i2][i3][i4][i5][i6]='Y'; break;
  198.     case 'Y': arry[i0][i1][i2][i3][i4][i5][i6]='N'; l=1; break;
  199.     case 'n': case 'N': arry[i0][i1][i2][i3][i4][i5][i6]='N'; break;
  200.     default: break; };
  201. };};};};};};};
  202. return l; }
  203.  
  204. /* pass4 - print loops which remain */
  205. pass4() {
  206. int i0, i1, i2, i3, i4, i5, i6;
  207. int j0, j1, j2, j3, j4, j5, j6, k, l, m;
  208. printf(" pass4 \015");
  209. for (i0=0; i0<4; i0++) {
  210. for (i1=0; i1<4; i1++) {
  211. for (i2=0; i2<4; i2++) {
  212. for (i3=0; i3<4; i3++) {
  213. for (i4=0; i4<4; i4++) {
  214. for (i5=0; i5<4; i5++) {
  215. for (i6=0; i6<4; i6++) {
  216. j1=i1; j2=i2; j3=i3; j4=i4; j5=i5; j6=i6;
  217. l=0;
  218. m=0;
  219. do {
  220.         if (arry[0][j1][j2][j3][j4][j5][j6]=='Y')
  221.     {arry[0][j1][j2][j3][j4][j5][j6]='y';
  222.     k=j6; j5=j4; j4=j3; j3=j2; j2=j1; j1=0; m=1;}
  223.   else {if (arry[1][j1][j2][j3][j4][j5][j6]=='Y')
  224.     {arry[1][j1][j2][j3][j4][j5][j6]='y';
  225.     k=j6; j5=j4; j4=j3; j3=j2; j2=j1; j1=1; m=1;}
  226.   else {if (arry[2][j1][j2][j3][j4][j5][j6]=='Y')
  227.     {arry[2][j1][j2][j3][j4][j5][j6]='y';
  228.     k=j6; j5=j4; j4=j3; j3=j2; j2=j1; j1=2; m=1;}
  229.   else {if (arry[3][j1][j2][j3][j4][j5][j6]=='Y')
  230.     {arry[3][j1][j2][j3][j4][j5][j6]='y';
  231.     k=j6; j5=j4; j4=j3; j3=j2; j2=j1; j1=3; m=1;}
  232.   else {l=1;
  233.     if (m==1) {j0=j1; j1=j2; j2=j3; j3=j4; j4=j5; j5=j6; j6=k;};
  234.     };};};};
  235.   } while (l==0);
  236. l=0; 
  237. m=0;
  238. do {
  239.         if (arry[j0][j1][j2][j3][j4][j5][0]=='y')
  240.    {prf(j0,j1,j2,j3,j4,j5,0);
  241.    arry[j0][j1][j2][j3][j4][j5][0]='N';
  242.    j0=j1; j1=j2; j2=j3; j3=j4; j4=j5; j5=0; m=1;}
  243.   else {if (arry[j0][j1][j2][j3][j4][j5][1]=='y')
  244.    {prf(j0,j1,j2,j3,j4,j5,1);
  245.    arry[j0][j1][j2][j3][j4][j5][1]='N';
  246.    j0=j1; j1=j2; j2=j3; j3=j4; j4=j5; j5=1; m=1;}
  247.   else {if (arry[j0][j1][j2][j3][j4][j5][2]=='y')
  248.    {prf(j0,j1,j2,j3,j4,j5,2);
  249.    arry[j0][j1][j2][j3][j4][j5][2]='N';
  250.    j0=j1; j1=j2; j2=j3; j3=j4; j4=j5; j5=2; m=1;}
  251.   else {if (arry[j0][j1][j2][j3][j4][j5][3]=='y')
  252.    {prf(j0,j1,j2,j3,j4,j5,3);
  253.    arry[j0][j1][j2][j3][j4][j5][3]='N';
  254.    j0=j1; j1=j2; j2=j3; j3=j4; j4=j5; j5=3; m=1;}
  255.   else {l=1;};};};};
  256.   } while (l==0);
  257. l=0;
  258. do {
  259.         if (arry[j0][j1][j2][j3][j4][j5][0]=='Y')
  260.    {prf(j0,j1,j2,j3,j4,j5,0);
  261.    arry[j0][j1][j2][j3][j4][j5][0]='N';
  262.    j0=j1; j1=j2; j2=j3; j3=j4; j4=j5; j5=0; m=1;}
  263.   else {if (arry[j0][j1][j2][j3][j4][j5][1]=='Y')
  264.    {prf(j0,j1,j2,j3,j4,j5,1);
  265.    arry[j0][j1][j2][j3][j4][j5][1]='N';
  266.    j0=j1; j1=j2; j2=j3; j3=j4; j4=j5; j5=1; m=1;}
  267.   else {if (arry[j0][j1][j2][j3][j4][j5][2]=='Y')
  268.    {prf(j0,j1,j2,j3,j4,j5,2);
  269.    arry[j0][j1][j2][j3][j4][j5][2]='N';
  270.    j0=j1; j1=j2; j2=j3; j3=j4; j4=j5; j5=2; m=1;}
  271.   else {if (arry[j0][j1][j2][j3][j4][j5][3]=='Y')
  272.    {prf(j0,j1,j2,j3,j4,j5,3);
  273.    arry[j0][j1][j2][j3][j4][j5][3]='N';
  274.    j0=j1; j1=j2; j2=j3; j3=j4; j4=j5; j5=3; m=1;}
  275.   else {l=1; if (m==1) kwait(0);};};};};
  276.   } while (l==0);
  277. };};};};};};};
  278. }
  279.  
  280. /* print one of the individual links in a chain */
  281. prf(i0,i1,i2,i3,i4,i5,i6)
  282. int i0, i1, i2, i3, i4, i5, i6; {
  283. kwait(1);
  284. printf("%1d",i0);
  285. printf("%1d",i1);
  286. printf("%1d",i2);
  287. printf("%1d",i3);
  288. printf("%1d",i4);
  289. printf("%1d",i5);
  290. printf("-");
  291. printf("%1d",i6);
  292. printf(" ");}
  293.  
  294. /* print the whole list of links - impractical except for debugging  */
  295. pall() {
  296. int i0, i1, i2, i3, i4, i5, i6;
  297. for (i0=0; i0<4; i0++) {
  298. for (i1=0; i1<4; i1++) {
  299. for (i2=0; i2<4; i2++) {
  300. for (i3=0; i3<4; i3++) {
  301. for (i4=0; i4<4; i4++) {
  302. for (i5=0; i5<4; i5++) {
  303. for (i6=0; i6<4; i6++) {
  304. printf("%c",arry[i0][i1][i2][i3][i4][i5][i6]);
  305. };};};};};};};
  306. printf("\n");
  307. }
  308.  
  309. /* keyboard status */
  310. kbdst() {return bdos(11)&0xFF;}
  311.  
  312. /* direct keyboard input, no echo */
  313. kbdin() {int c;
  314. if ((c=bdos(7)&0xFF)=='\0') c=(bdos(7)&0xFF)|0x80;
  315. return c;}
  316.  
  317. /* pause at the end of a full screen */
  318. kwait(i) int i; {
  319. switch (i) {
  320.   case 0: printf("\n"); nc=0; nl++; break;
  321.   case 1: {if (nc==MC) {printf("&\n"); nc=1; nl++;} else nc++;}; break;
  322.   default: break;};
  323. if (nl==ML) {
  324.   nl=0;
  325.   printf(" press any key to continue\015");
  326.   while (kbdst()) {};
  327.   kbdin();
  328.   printf("-                         \n");
  329.   };
  330. }
  331.  
  332. /* end */
  333.